--[[
	哈希函数
	哈希表中的key就是通过函数转换为一个整数
	哈希函数会有冲突 f(key1) = f(key2) , key1 ~= key2, 哈希表会用链表法解决这个问题
--]]
local string = string
local string_len = string.len
local string_byte = string.byte
local math = math

--数字转为2进制(字符串表示
local function tobinary(num)
	local tmp = num
	local str = ""
	repeat
		if tmp % 2 == 1 then
			str = str.."1"
		else
			str = str.."0"
		end
		tmp = math.modf(tmp/2)
	until(tmp == 0)
	str = string.reverse(str)
	return str
end

--异或
local function xor(num1,num2)
	local str1 = tobinary(num1)
	local str2 = tobinary(num2)
	local len1 = string_len(str1)
	local len2 = string_len(str2)
	local len = 0
	local x = 0
	local tmp = ""
	if len1 > len2 then
		x = len1 - len2
		for i=1,x do
			str2 = "0"..str2
		end
		len = len1
	elseif len2 > len1 then
		x = len2 - len1
		for i=1,x do
			str1 = "0"..str1
		end
		len = len2
	end
	for i=1,len do
		local s1 = string.sub(str1,i,i)
		local s2 = string.sub(str2,i,i)
		if s1 == s2 then
			tmp = tmp.."0"
		else
			tmp = tmp.."1"
		end
	end
	--tmp = string.reverse(tmp)
	return tonumber(tmp,2)
end

local Hash = {}

function Hash.new(...)
	local instance = setmetatable({}, {__index=Hash})
	instance:ctor(...)
	return instance
end

function Hash:ctor()
	self.seed = 2022
end

-- HashSeed return hash of the given data, using specified seed
function Hash:encode(data , seed)
	-- Similar to murmur hash
	if type(data) ~= "string" then
		print("warring encode data is not string!", type(data))
		local ok, res = pcall(tostring, data)
		if not ok then
			error("encode data is can not to string!")
			return
		end
		data = res
	end
	if not seed then
		seed = self.seed
	end
	local m = 0xc6a4a793
	local r = 24
	local h = xor(seed, (string_len(data) * m))
	local len = string_len(data)
	local n = len - len%4
	local i = 1
	for i=1, n do
		h = h + string_byte(data,i)
		h = h * m
		h = xor(h ,(h >> 16))
		i = i + 4
	end
	if len - i == 3 then
		h = h + (string_byte(data, i + 2) << 16)
	elseif len - i == 2 then
		h = h + (string_byte(data, i + 1) << 8)
	elseif len - i == 1 then
		h = h + (string_byte(data, i))
		h = h * m
		h = xor(h, (h >> r))
	elseif len - i == 0 then
	end

	return h
end



------------------------------------------------------------------
--测试
------------------------------------------------------------------
if arg and arg[0] == "hash.lua" then
	local hash = Hash.new()
	local data = "123467123467dsddsadaasdad213412412346712346712346712346712\
	12346712346712346712346712346712346712\
	12346712346712346712346712346712346712\
	12346712346712346712346712346712346712\
	12346712346712346712346712346712346712\
	3467123467123467123467123467123467"
	local key = hash:encode(data)
	print(key, type(key))

	local str = tostring(key)
	print(string.len(str))
	local data = {111}
	print(hash:encode(data))
end



return Hash

